﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

#include <stack>
#include <vector>

struct TreeNode 
{
	int val;
	TreeNode* left;
	TreeNode* right;

	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution 
{
public:
	vector<int> inorderTraversal(TreeNode* root) 
	{
		stack<TreeNode*> st;
		TreeNode* cur = root;
		vector<int> v;

		while (cur || !st.empty())
		{
			// 访问⼀颗树的开始
			// 1、左路结点⼊栈
			while (cur)
			{
				st.push(cur);
				cur = cur->left;
			}

			// 访问问左路结点 和 左路结点的右⼦树
			TreeNode* top = st.top();
			st.pop();
			v.push_back(top->val);

			// 循环⼦问题⽅式访问右⼦树
			cur = top->right;
		}

		return v;
	}
};

int main()
{
	// root = [1,null,2,3]

	TreeNode* root = new TreeNode(1);
	
	root->right = new TreeNode(2);

	root->right->left = new TreeNode(3);

	auto v = Solution().inorderTraversal(root);

	for (const auto& num : v) cout << num << " ";
	cout << endl;

	return 0;
}
